package com.wudeyong;

import java.io.*;
import java.util.*;

/**
 * Author :wudeyong
 * Date 2017/6/27
 * For More Information,Please Visit https://wudeyong.com
 */
public class Apriori2 {
    private  static int SUPPORT = 186; // 支持度阈值
    private final static String ITEM_SPLIT = ";"; // 项之间的分隔符
    private static String[] nameMapper;

    /**
     * 算法主程序
     * @param dataList
     * @return
     */
    public Map<String, Integer> apriori(ArrayList<String> dataList)
    {
        Map<String, Integer> stepFrequentSetMap = new HashMap<String, Integer>();
        stepFrequentSetMap.putAll(findFrequentOneSets(dataList));

        Map<String, Integer> frequentSetMap = new HashMap<String, Integer>();//频繁项集
        Map<String,Integer> maxLK=new HashMap<String, Integer>();
//        frequentSetMap.putAll(stepFrequentSetMap);

        while(stepFrequentSetMap!=null && stepFrequentSetMap.size()>0)
        {
            Map<String, Integer> candidateSetMap = aprioriGen(stepFrequentSetMap);

            Set<String> candidateKeySet = candidateSetMap.keySet();

            //扫描D，进行计数
            for(String data:dataList)
            {
                for(String candidate:candidateKeySet)
                {
                    boolean flag = true;
                    String[] strings = candidate.split(ITEM_SPLIT);
                    for(String string:strings)
                    {
                        if(data.indexOf(string+ITEM_SPLIT)==-1)
                        {
                            flag = false;
                            break;
                        }
                    }
                    if(flag)
                        candidateSetMap.put(candidate, candidateSetMap.get(candidate)+1);
                }
            }

            //从候选集中找到符合支持度的频繁项集
            stepFrequentSetMap.clear();
            for(String candidate:candidateKeySet)
            {
                Integer count = candidateSetMap.get(candidate);
                if(count>=SUPPORT)
                    stepFrequentSetMap.put(candidate, count);
            }
            if(stepFrequentSetMap.size()!=0)
            {
                maxLK.clear();
                maxLK.putAll(stepFrequentSetMap);
            }

        }
//最大频繁项集
        return maxLK;
    }

    /**
     * 发现1-频繁项集
     * @param dataList
     * @return
     */
    private Map<String, Integer> findFrequentOneSets(ArrayList<String> dataList)
    {
        Map<String, Integer> resultSetMap = new HashMap<String, Integer>();

        for(String data:dataList)
        {
            String[] strings = data.split(ITEM_SPLIT);
            for(String string:strings)
            {
                string += ITEM_SPLIT;
                if(resultSetMap.get(string)==null)
                {
                    resultSetMap.put(string, 1);
                }
                else {
                    resultSetMap.put(string, resultSetMap.get(string)+1);
                }
            }
        }
        return resultSetMap;
    }

    /**
     * 根据上一步的频繁项集的集合选出候选集
     * @param setMap
     * @return
     */
    private Map<String, Integer> aprioriGen(Map<String, Integer> setMap)
    {
        Map<String, Integer> candidateSetMap = new HashMap<String, Integer>();

        Set<String> candidateSet = setMap.keySet();
        for(String s1:candidateSet)
        {
            String[] strings1 = s1.split(ITEM_SPLIT);
            String s1String = "";
            for(String temp:strings1)
                s1String += temp+ITEM_SPLIT;

            for(String s2:candidateSet)
            {
                String[] strings2 = s2.split(ITEM_SPLIT);


                boolean flag = true;
                for(int i=0;i<strings1.length-1;i++)
                {
                    if(strings1[i].compareTo(strings2[i])!=0)
                    {
                        flag = false;
                        break;
                    }
                }
                if(flag && strings1[strings1.length-1].compareTo(strings2[strings1.length-1])<0)
                {
                    //连接步：产生候选
                    String c = s1String+strings2[strings2.length-1]+ITEM_SPLIT;
                    if(hasInfrequentSubset(c, setMap))
                    {
                        //剪枝步：删除非频繁的候选
                    }
                    else {
                        candidateSetMap.put(c, 0);
                    }
                }
            }
        }

        return candidateSetMap;
    }

    /**
     * 使用先验知识，判断候选集是否是频繁项集
     * @param setMap
     * @return
     */
    private boolean hasInfrequentSubset(String candidateSet, Map<String, Integer> setMap)
    {
        String[] strings = candidateSet.split(ITEM_SPLIT);

        //找出候选集所有的子集，并判断每个子集是否属于频繁子集
        for(int i=0;i<strings.length;i++)
        {
            String subString = "";
            for(int j=0;j<strings.length;j++)
            {
                if(j!=i)
                {
                    subString += strings[j]+ITEM_SPLIT;
                }
            }

            if(setMap.get(subString)==null)
                return true;
        }

        return false;
    }



    public static void main(String[] args)
    {
        ArrayList<String> dataList ;
//        从文件获取数据
        dataList=getDataFromFile("C:\\Users\\TeenTeam\\Desktop\\大数据\\dataset.txt");
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入支持度阈值：");
        SUPPORT=scanner.nextInt();
//        for(String string:dataList)
//        {
//            System.out.println(string);
//        }

        Apriori2 apriori2 = new Apriori2();

        System.out.println("=========最大频繁项集为==========");

        Map<String, Integer> frequentSetMap = apriori2.apriori(dataList);
        Set<String> keySet = frequentSetMap.keySet();
        for(String key:keySet)
        {

            String[] tmp=key.split(";");
            String desc="";
//            拼接名称，使得人可识别
            for(int i=0;i<tmp.length;i++){
                desc+=nameMapper[Integer.parseInt(tmp[i])]+";";
            }
            System.out.println(desc+" : "+frequentSetMap.get(key));
        }


    }

    public static ArrayList getDataFromFile(String filePath){
        File file=new File(filePath);
        ArrayList<String> data=new ArrayList<String>();
        String tmp,carsData;
        try {
            InputStreamReader reader=new InputStreamReader(new FileInputStream(file));
            BufferedReader bufferedReader=new BufferedReader(reader);
            tmp=bufferedReader.readLine();
            nameMapper=tmp.split("\t");
            while ((tmp=bufferedReader.readLine())!=null){
                carsData="";
                String[] spilt=tmp.split("\t");
                for(int i=1;i<spilt.length;i++)
                    if (spilt[i].equals("T"))
                        carsData+=i+";";
                if(!carsData.equals(""))
                {
                    data.add(carsData);
                }

            }

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return data;
    }
}
